\section{Experiments}\label{sec:exp}

We solved all $77$ problems. Figure \ref{fig:nback} shows the number of backtrackings for each problem. The ``naked triple (double)'' strategy exhibits impressive performance in constraint propagations. Without such kinds of rules, there are $1/4$ problems that need to use backtracking, no matter if we pick the most constrained slot or pick a slot randomly. Meanwhile, only $2$ or $3$ problems require backtracking for the ``naked triple'' case. 

\begin{figure}[ht]
\centering
\begin{tabular}{cc}
\subfloat[Rule 1]{\includegraphics[scale=0.32]{../results/bt-r1-bt.pdf}} 
   & \subfloat[Rule 1,2]{\includegraphics[scale=0.32]{../results/bt-r1-r2-bt.pdf}}\\
\subfloat[Rule 1 + Naked double and triple]{\includegraphics[scale=0.32]{../results/bt-r1-n23-bt.pdf}} 
   & \subfloat[Rule 1,2 + Naked double and triple]{\includegraphics[scale=0.32]{../results/bt-r1-r2-n23-bt.pdf}}\\
%\subfloat[E]{\includegraphics[width=2cm]{logo}} 
%   & \subfloat[F]{\includegraphics[width=3cm]{logo}}\\
\end{tabular}
\caption{Number of backtracing with respect to each problem.}
\label{fig:nback}
\end{figure}

Next we show the problem completion in each difficulty level in table \ref{tab:dif}. As one introduces more rules, more puzzles are solvable. By adding backtracking search, all problems are solvable. This makes sense because backtracking search would have to go through all possible assignments.

\begin{table}[!h]
    \centering
    \scalebox{0.8}{
	    \begin{tabular}{|l|c|c|c|c|c|c|c|}
		\hline
		Complexity   & r1 & r1,2 & r1,2+n2 & r1,2+n3 & r1,2+n2,3 & r1,2+bt & r1,2+n2,3+bt \\ \hline
		Easy (23):   & 21 & 21 & 23 & 23 & 23 & 23 & 23 \\ \hline
		Medimum (21) & 3 & 3 & 10 & 14 & 19 & 21 & 21 \\ \hline
		Hard (18)    & 0 & 0 & 7 & 4 & 15 & 18 & 18 \\ \hline
		Evil (15)    & 3 & 3 & 4 & 3 & 8 & 15 & 15 \\ \hline
        \hline
		Easy rand:   & 21 & 21 & 23 & 23 & 23 & 23 & 23 \\ \hline
		Medimum rand & 3 & 3 & 10 & 14 & 19 & 21 & 21 \\ \hline
		Hard rand    & 0 & 0 & 7 & 4 & 15 & 18 & 18 \\ \hline
		Evil rand    & 3 & 3 & 4 & 3 & 8 & 15 & 15 \\ \hline
	    \end{tabular}
    }
    \caption{Number of complete problems in different combinations of rules. The default heuristic is the most constrained slot. Picking the most constrained slot or picking random slot is the same. Here, r1: rule 1, r1,2: rule1 + rule2, n2: naked double, n3: naked triple, n2,3: n2 + n3.}\label{tab:dif}
\end{table}

For comparing the effectiveness of most constrained slot heuristic and random slot heuristic, we make the same experiment with random slot heuristic, which placed in last 4 rows in table \ref{tab:dif}. These two heuristics are getting same results, which confirms they are both functioning. However performance-wise, the number of backtrackings for using the constrained slot heuristic is severely reduced when compared to the random slot heuristic as shown in the previous figure \ref{fig:nback}. From the graph, in just using rule one and backtracking, the random slot heuristic yields hundreds of backtracking for certain problems whereas the most constrained heuristic solves in less significantly less than one hundred backtrackings. Of course, the random heuristic is random so one does expect the random heuristic to perform well sometimes.

For justifying the difficulty of problems, the average number of filled-in numbers are concerned, as shown in table \ref{tab:fill}.

\begin{table}[!h]
    \centering
    \scalebox{0.9}{
	    \begin{tabular}{|l|c|c|c|c|}
		\hline
		             & easy & medimum & hard & evil \\ \hline
		average number & 34.70 & 29.05 & 26.28 & 26.13 \\ \hline
	    \end{tabular}
    }
    \caption{Average filled-in numbers for each problem level.}\label{tab:fill}
\end{table}

The number of rules being used is an important factor. We also use it to estimate the difficulty of a problem and show the average number of different kinds of rules used for each set of problems. The results are shown in table \ref{tab:rule}. The trend is clear that more hard problems requires more number of rules. Note that for this experiment we use the combination of all rules and backtracking for making sure every problem can be solved.

\begin{table}[!h]
    \centering
    \scalebox{0.8}{
	    \begin{tabular}{|l|c|c|c|c|c|c|c|}
		\hline
		             & r1 & r2 & n2 & n3 & bt \\ \hline
		Easy (23):   & 42.26 & 0.04 & 22.00 & 12.70 & 0 \\ \hline
		Medimum (21) & 46.95 & 0.14 & 31.14 & 16.81 & 0 \\ \hline
		Hard (18)    & 49.06 & 0.33 & 32.11 & 15.94 & 0.06 \\ \hline
		Evil (15)    & 59.40 & 0 & 38.20 & 22.33 & 0.60 \\ \hline
	    \end{tabular}
    }
    \caption{Average number of rules used by problems in different levels. Here, r1: rule 1, r2: rule2, n2: naked double, n3: naked triple, bt: number of backtrackings.}\label{tab:rule}
\end{table}

We further compare with two heuristics in the number of rules being taken. Figure \ref{fig:heu} shows all pair of comparisons. By applying these two heuristics, a problem uses more or less the same number of rules. This is consistent with our experiment in the number of complete problems. 

\begin{figure}[ht]
\centering
\begin{tabular}{cc}
\subfloat[Rule 1]{\includegraphics[scale=0.32]{../results/bt-r1-r2-n23-rule1.pdf}} 
   & \subfloat[Rule 2]{\includegraphics[scale=0.32]{../results/bt-r1-r2-n23-rule2.pdf}}\\
\subfloat[Naked double]{\includegraphics[scale=0.32]{../results/bt-r1-r2-n23-naked2.pdf}} 
   & \subfloat[Naked triple]{\includegraphics[scale=0.32]{../results/bt-r1-r2-n23-naked3.pdf}}\\
%\subfloat[E]{\includegraphics[width=2cm]{logo}} 
%   & \subfloat[F]{\includegraphics[width=3cm]{logo}}\\
\end{tabular}
\caption{Comparisons between most constrained slot heuristic and random slot heuristic in number of rules taken.}
\label{fig:heu}
\end{figure}
%
%\begin{table}[!h]
%    \centering
%    \scalebox{0.9}{
%	    \begin{tabular}{|l|c|c|c|c|c|c|c|}
%		\hline
%		Disks: & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ \hline
%		A*/admissible & 8.8 & 11.6 & 13.95 & 16.5 & 18.6 & n/a & n/a\\ \hline
%		%A*/admissible H7 & 8.95 & 11.6 & 13.95 & 16.75 & 19.2 & 22.4 & 24.77\\ \hline
%		RBFS/admissible & 8.8 & 11.6 & 13.95 & 16.35 & 17.11 & n/a & n/a\\ \hline
%		A*/nonadmissible 1 & 8.85 & 11.85 & 14.6 & 17.5 & 20.2 & 24.1 & 27.6\\ \hline
%		RBFS/nonadmissible 1 & 8.85 & 11.85 & 15.25 & 19 & 22.21 & 26.81 & 32.25 \\ \hline
%		A*/nonadmissible 2 & 9.25 & 12.95 & 16.5 & 20.05 & 23.8 & 27.4 & 34.05\\ \hline
%		RBFS/nonadmissible 2 & 11.25 & 17.85 & 24.35 & 32.75 & 40.35 & 50.7 & 64.55\\ \hline
%	    \end{tabular}
%    }
%    \caption{Average solution length per algorithm, heuristic and disk size. n/a means unable to compute within 10 minutes for all problems. Note that some experiments failed for completing before NMAX nodes; these were not included in the average.}\label{tab:solen}
%\end{table}
